package genericorderedlist;
import java.util.Comparator;
import java.util.Iterator;
import java.util.ListIterator;


public class ListUtil {
	
	public static<E extends Comparable<? super E>> Comparator<E> naturalOrder() {
		return new Comparator<E>() {
			@Override
			public int compare(E o1, E o2) {
				return o1.compareTo(o2);
			}
			
		};
	}
	
	public static<E> Comparator<E> reverseOrder(final Comparator<E> cmp) {
		return new Comparator<E>() {
			@Override
			public int compare(E o1, E o2) {
				return cmp.compare(o2, o1);
			}
		};
	}
	
	
	public static<E> boolean add(Comparator<? super E> cmp, OrderedList<E> l, E e1) {
		if (e1==null)
			throw new NullPointerException();
		
		ListIterator<E> it = l.listIterator();

		while (it.hasNext()) {
			int comp = cmp.compare(it.next(),e1);
			
			if (comp < 0)
				continue;
			if (comp > 0) {
				it.previous();
				break;
			} else
				return false;
		}
		
		it.add(e1);
		return true;
	}
	
	/**
	 * inserts all elements returned by the iterator src 
	 * in the ordered list dst, respecting the natural order 
	 * of the elements of dst. 
	 * Returns true iff at least one element has been inserted
	 * @param <E>
	 * @param src
	 * @param dst
	 */
	public static<E> boolean addAll(Comparator<? super E> cmp, Iterable<? extends E> src, OrderedList<E> dst) {		
		boolean ris = false;
		for (E srcEl: src) {
			ris |= add(cmp, dst, srcEl);
		}
		return ris;
	}
	
	
	/**
	 * returns the list iterator where the element == el
	 * @param l
	 * @param e1
	 * @return
	 */
	private static<E> ListIterator<? extends E> getElem(Comparator<? super E> cmp, OrderedList<? extends E> l, E e1){
		ListIterator<? extends E> it = l.listIterator();
		
		while (it.hasNext()) {
			int ris = cmp.compare(it.next(), e1);
			if (ris == 0) {
				return it;
			}
			if (ris > 0)
				return null;
		}
		
		return null;
	}
	
	/**
	 * returns true iff the ordered list l contains el.
	 * @param <E>
	 * @param l
	 * @param e
	 * @return
	 */
	public static<E> boolean contains(Comparator<? super E> cmp, OrderedList<? extends E> l, E e1) {
		return getElem(cmp, l, e1) != null;
	}
	
	/***
	 * removes the element el from the ordered list l. 
	 * Returns true iff the element has been removed
	 * @param <E>
	 * @param l
	 * @param e1
	 * @return
	 */
	public static<E> boolean remove(Comparator<? super E> cmp, OrderedList<? extends E> l, E e1) {
		ListIterator<? extends E> it = getElem(cmp, l, e1);
		if (it == null)
			return false;
		it.remove();
		return true;
	}
	
	/***
	 * returns true iff the two (not necessarily ordered) 
	 * lists l1 and l2 are equals, that is, they are both 
	 * instances of List, have the same size, and same elements 
	 * (possibly null) at the same position
	 * @param <E>
	 * @param src
	 * @param dst
	 * @return
	 */
	public static boolean equals(List<?> src, List<?> dst) {
		if (src == null || dst == null)
			return false;
		if (src == dst)
			return true;
		if (src.size() != dst.size()) 
			return false;
		Iterator<?> srcIt = src.iterator();
		Iterator<?> dstIt = dst.iterator();
		
		while (srcIt.hasNext() && dstIt.hasNext()) {
			Object srcE = srcIt.next();
			Object dstE = dstIt.next();
			
			if (srcE == null)
				if (dstE == null)
					continue;
				else
					return false;
			
			if (!srcE.equals(dstE))
				return false;
		}
		
		return true;
	}
	
	/***
	 * compares the two (not necessarily ordered) lists l1 and l2 
	 * by using the lexicographical order induced by the natural 
	 * order defined on the elements of the two lists
	 * @param <E>
	 * @param src
	 * @param dst
	 * @return
	 */
	public static<E> int compareTo(Comparator<? super E> cmp, List<? extends E> src, List<? extends E> dst) {
		Iterator<? extends E> srcIt = src.iterator();
		Iterator<? extends E> dstIt = dst.iterator();
		
		int ris = 0;
		while (srcIt.hasNext() && dstIt.hasNext()) {
			ris = cmp.compare(srcIt.next(), dstIt.next());
			
			if (ris != 0)
				return ris;
		}
		
		if (!srcIt.hasNext()) {
			if (!dstIt.hasNext())
				return 0;
			return -1;
		}
		
		return 1;			
	}
	
	public static<E> void merge(Comparator<? super E> cmp, OrderedList<? extends E> src, OrderedList<E> dst){
		if (src==dst)
			return;
		
		ListIterator<? extends E> srcIt = src.listIterator();
		ListIterator<E> dstIt = dst.listIterator();
		
		while (srcIt.hasNext() && dstIt.hasNext()) {
			E srcEl = srcIt.next();
			int res = 0;
			while (dstIt.hasNext() && (res = cmp.compare(srcEl, dstIt.next())) > 0);
			if (res == 0) continue;
			if (res < 0)
				dstIt.previous();
			dstIt.add(srcEl);
		}
		
		while (srcIt.hasNext())
			dstIt.add(srcIt.next());
	}
	
	public static<E> E max(Comparator<? super E> cmp, List<? extends E> list) {
		Iterator<? extends E> it = list.iterator();
		E toReturn = it.next();

		while (it.hasNext()) {
			E another = it.next();
			if (cmp.compare(toReturn, another) < 0)
				toReturn = another;
		}
		
		return toReturn;
	}
	
	public static<E> E max(OrderedList<? extends E> ordList) {
		return ordList.listIterator(ordList.size()).previous();
	}
	
	private static<E> void auxReverse(List<E> list) {
		ListIterator<E> forward_it = list.listIterator();
		ListIterator<E> backward_it = list.listIterator(list.size());
		
		E forward_el, backward_el;
		while (forward_it.nextIndex() < backward_it.nextIndex()) {
			forward_el = forward_it.next();
			backward_el = backward_it.previous();
			forward_it.set(backward_el);
			backward_it.set(forward_el);
		}
	}
	
	public static void reverse(List<?> list) {
		auxReverse(list);
	}
}